package com.sicheng.algorithm.array.sorted;

import java.util.Arrays;

/**
 * 基数排序
 *
 * @author zsc
 * @version 1.0
 * @date 2021/8/28 12:36
 */
public class RadixSorted {
    /*
     * 获取数组arr中最大值
     *
     * 参数说明：
     *     arr -- 数组
     *     n -- 数组长度
     */
    private static int getMax(int[] arr) {
        int max;
        max = arr[0];
        for (int i = 1; i < arr.length; i++)
            if (arr[i] > max)
                max = arr[i];
        return max;
    }

    /*
     * 对数组按照"某个位数"进行排序(桶排序)
     *
     * 参数说明：
     *     a -- 数组
     *     exp -- 指数。对数组a按照该指数进行排序。
     *
     * 例如，对于数组a={50, 3, 542, 745, 2014, 154, 63, 616}；
     *    (01) 当exp=1=10^0,表示按照"个位"对数组arr进行排序
     *    (02) 当exp=10=10^1,表示按照"十位"对数组arr进行排序
     *    (03) 当exp=100=10^2,表示按照"百位"对数组arr进行排序
    /*
     * 基数排序
     *
     * 参数说明：
     *     a -- 数组
     */
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 指数。当对数组按各位进行排序时，exp=1；按十位进行排序时，exp=10；...
        int max = getMax(arr);    // 数组a中的最大值
        int maxLen = String.valueOf(max).length();//数组元素最大值的位数
        // 从个位开始，对数组arr按"指数"进行排序
        int[][] bucket = new int[10][arr.length];
        int[] count = new int[10];

        for (int i = 0; i < maxLen; i++) {
            //将数组中元素按规则放入桶中
            for (int e : arr) {
                int radix = (int) (e / Math.pow(10, i) % 10);
                bucket[radix][count[radix]++] = e;
            }
            //从桶中取出元素写回数组
            int k = 0;
            for (int radix = 0; radix < count.length; radix++) {
                if (count[radix] > 0) {
                    for (int j = 0; j < count[radix]; j++) {
                        arr[k++] = bucket[radix][j];
                    }
                    count[radix] = 0;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {53, 3, 542, 748, 14, 214, 154, 63, 616, 0};
        System.out.println("before sort:");
        System.out.println(Arrays.toString(arr));
        System.out.println();
        long start = System.currentTimeMillis();
        radixSort(arr);    // 基数排序
        long end = System.currentTimeMillis();
        System.out.println("after  sort:");
        System.out.println(Arrays.toString(arr));
        System.out.println("用时:" + (end - start) + "ms");
    }


}
